As semiconductor technology progresses, more and more complex logic functions are desired on a single integrated circuit. In recent years, various techniques for implementing complex combinational logic in multiple level formats have been developed. Multiple level logic contains intermediate signals in addition to inputs and outputs. Multilevel optimization of this logic involves creating new intermediate signals and/or removing some of the existing intermediate signals. The traditional optimization criterion for multilevel logic synthesis is to minimize the area occupied by the logic equations (which is measured as a function of the number of gates, transistors, and nets in the final set of equations) while simultaneously satisfying the timing constraints derived from a system level analysis of the chip.
One technique for multilevel optimization is the Multilevel Logic Interactive Synthesis System (MIS). (See, R. Brayton et. al., "MIS: A Multiple-Level Logic Optimization System", IEEE Trans. on Computer-Aided Design, November, 1987, pp. 1062-1081.) The input to the optimization process is a set of boolean functions. A procedure, called Kernel, finds some or all cube-free multiple or single cube divisors of each of the functions and retains those divisors which are common to two or more functions. The best few common divisors are factored out and the affected functions are simplified by a second procedure called substitution. Kernel, selection of the best few divisors, and substitution are repeated until no common divisors can be found. The "goodness" of a divisor is measured by the magnitude of area saving it brings about.
Although multilevel logic optimizers such as MIS are a vast improvement over prior methods, the basic optimization criterion is limited to minimizing area while still satisfying time constraints.